/**
 * @brief 跳表的实现
 * @version 1.0
 * @author 宋炜
 * @date 2024-01-24
*/

#pragma once

#include <list>
#include <type_traits>
#include <vector>
#inlucde <memory>
#include <mutex>

template< typename T >
class skipList
{
public:
	using value_type = typename std::remove_pointer< typename std::decay< T > ::type >::type;

	struct stNode{
		value_type     m_value;
		std::shared_ptr< stNode >     pt_next;     // 后继节点
		std::shared_ptr< stNode >     pt_pre;      // 前驱节点
		std::shared_ptr< stNode >     pt_down;     // 下行节点
	};
	
	struct stHead{
		size_t                        m_count;     // 本层数据数量
		std::shared_ptr< stNode >     pt_data;     // 数据头
		
		stHead():m_count(0){}
	};
	
	class stIterator : public std::iterator< bidirectional_iterator_tag >{
	private:
		stNode * p_node__;
	public:
		stIterator():p_node__( nullptr ){}
		stIterator( stNode * node ):p_node__( node ){}
	}
	
	using iterator = stIterator;
protected:
	std::vector< stHead >     m_head__;
	std::mutex                m_mutex__;
protected:
	/**
	 * @brief 计算层数
	 * @param nodeCount[ I ], 数据点数量
	*/
	size_t level_count__( size_t nodeCount ){
		size_t ret = 0; c = nodeCount;
		for( ;; ret ++ ){
			c >>= 1;
			if( c <= 3 && c > 1 ){
				break;
			}
		}
		
		return ret;
	}
public:
	skipList(){}
	skipList( size_t s ): m_head__( s ){
		
	}
	virtual ~skipList(){}
	/**
	 * @brief 插入节点
	 * @param 要插入的数据
	*/
	bool insert( const value_type& data ){
		bool ret = false;
		size_t cl = m_head__.size() , new_level = level_count__( m_head__[ 0 ].m_count + 1 );
		if( new_level > c1 ){
			m_head__.push_back( stHead );
		}else{
			
		}
		
		return ret;
	}
	
	void erase( iterator it ){
		
	}
	
	void erase( iterator start , iterator end ){
		
	}
	/**
	 * @brief 
	*/
	template< typename KEY_TYPE >
	iterator find_if( KEY_TYPE&& key , std::function< int ( KEY_TYPE&& , const value_type& ) > compare ){
		size_t cl = m_head__.size() - 1;
		if( cl == 0 ) return iterator(nullptr);
		iterator ret;
		// 从第一层开始找
		stNode * p_node = m_head__[ cl ].pt_data.get();
		while( p_node ){
			// 找到数据，则将指针移动到最后一层。使用这一层的数据作为实际返回的内容
			if( compare( std::forward< KEY_TYPE >( key ) ,  p_node->m_value ) == 0 ){
				while( p_node->p_down ){
					p_node = p_node->p_down.get();
				}
				
				ret.set( p_node );
				break;
			}else if( compare( std::forward< KEY_TYPE >( key ) ,  p_node->m_value ) < 0 ){ 
				cl --;
				if( cl < 0 ){ return ret; }
				if( p_node = p_node->p_pre ){	
					p_node = p_node->p_pre->p_down.get();
				}else{
					p_node = m_head__[ c1 ].pt_data.get();
				}
			}else{
				p_node = p_node->p_next.get();
			}
		}
	}
	/**
	 * 查找数据
	 * @param data 要查找的数据。数据类型如果比较复杂，应该重载 = 和 <
	*/
	iterator find( const value_type& data ){
		size_t cl = m_head__.size() - 1;
		if( cl == 0 ) return iterator(nullptr);
		iterator ret;
		// 从第一层开始找
		stNode * p_node = m_head__[ cl ].pt_data.get();
		while( p_node ){
			// 找到数据，则将指针移动到最后一层。使用这一层的数据作为实际返回的内容
			if( p_node->m_value == data ){
				while( p_node->p_down ){
					p_node = p_node->p_down.get();
				}
				
				ret.set( p_node );
				break;
			}else if( p_node->m_value < data ){ 
				cl --;
				if( cl < 0 ){
					return ret;
				}
				if( p_node = p_node->p_pre ){	
					p_node = p_node->p_pre->p_down.get();
				}else{
					p_node = m_head__[ c1 ].pt_data.get();
				}
			}else{
				p_node = p_node->p_next.get();
			}
		}
		
		return ret;
	}
	
	
};